It is well know by those skilled in the art that messages can be authenticated using an encryption algorithm operated in the cipher block chaining (“CBC”) mode to generate a message authentication code (“MAC”). Two disadvantages of using CBC mode for authentication are key management complexity and possible compromise due to forgery extension.
Sharing keys between security services (e.g., confidentiality, authentication, etc.) can potentially compromise the security of the entire system; if a shared key for one security service is compromised due to weakness in either the design of the security service, the security algorithms, or the particular implementation of the security service, then the shared key is compromised for all security services in which the key is shared. Therefore, it is common practice, and rightfully so, to use separate and independent keys for different security services. This, however, increases the number of keys used in a system, and thus greatly increases the key management complexity of that system. For a small system with a limited number of users and cryptographic devices, this may not be an issue, but as the size of the system and number of cryptographic devices increases, the complexity and burden of key management greatly increases. For large systems that use authentication as well as other security services, the key management requirements can easily exceed the users management capabilities as well as the performance abilities of the system to distribute keys.
The internal structure of CBC-MAC facilitates the possibility of forging a message by simply collecting message-MAC pairs; this has been published and discussed widely in academic literature. By collecting enough message-MAC pairs to find two different messages with the same MAC and also having the same resulting MAC after an identical arbitrary string is appended to both messages, a message with an authentic MAC can be forged. This type of an attack against CBC-MAC is known as a forgery extension attack. A possible solution to a forgery extension attack is to manage different keys for authenticating keys of different lengths, thus increasing the key management needs further.
Some solutions for easing the key management and forgery extension issues have been proposed. To solve the key management problem, systems can use a public key infrastructure (“PKI”) based on public key cryptography to either provide digital signatures for authentication or to allow for automatic key exchange or key agreement of authentication keys as well as keys for other security services. PKI, however, can increase the cost of development as well as the cost of the system as other devices are needed, such as a certificate authority. PKI also comes with its complexity as certificate revocation lists (“CRLs”) must be maintained and distributed. Public key cryptography has its own disadvantages in that it tends to be slower, requires more bandwidth for communication, and the state of the art does not allow for simultaneous multipoint key agreement or key exchange.
Other MAC algorithms have also been proposed based on constructions other than CBC-MAC that do not succumb to forgery extension attacks. For example, hash message authentication code (“HMAC”) is based on using hash algorithms, such as message digest v5 (“MD5”) or secure hash algorithm v1 (“SHA-1”), with a secret key to generate MACs. The disadvantage here is one of interoperability and engineering resources. CBC-MAC has been an established authentication mechanism for many years, and as such, millions of existing devices, protocols, and standards use CBC-MAC, making CBC-MAC necessary to easily retrofit these architectures with a replacement. Many of these systems also have limited resources (millions of instructions per second (“MIPS”), memory, gates, etc.) such that the ability to use core constructions between security services is necessary. The ability to use a core construction for authentication and other security services such as confidentiality is an advantage for these systems. Solutions, such as HMAC, for example, cannot be reused for confidentiality that makes these solutions less than acceptable, but CBC can be used in both authentication and confidentiality. Because the current state of the art public key cryptography technologies are not acceptable for confidentiality, except for key distribution, due to performance and require significant redesign of existing devices, systems, and standards, PKI is also not an acceptable replacement.
Thus, there exists a need to eliminate the forgery extension attack and reduce the number of keys to be managed by a device and/or system. At the same time, it is necessary that the replacement methodology be easy to retrofit into currently implemented systems using a minimum of resources.